跳至主要内容

Digit Queries

題目​

考慮一個按照遞增順序包含所有正整數的無窮字串： 12345678910111213141516171819202122232425...

你的任務是處理 qq 個查詢：第 kk 個字元是什麼數字？

輸入​

  • 第一行輸入一個正整數 qq，代表查詢的數量。（1≤q≤10001 \le q \le 1000）
  • 接著有 qq 行，每行有一個正整數 kk。（1≤k≤10181 \le k \le 10^{18}）

輸出​

輸出 qq 行，各自對應一個查詢。 對每個查詢，輸出字串第 kk 個字元。

範例測資​

Input :
3
7
19
12

Output :
7
4
1

解釋如下：

1234567891011121314151617181920...
^     ^    ^      ^
1     7   12     19

想法​

我們可以找第 kk 個字元落在哪個正整數 nn 裡面，又是 nn 從高位開始算起的哪一位數，從而找出答案。比如第 266266 個字元落在正整數 125125 裡面，並且是 125125 從高位開始算起的第 22 位數，所以第 266266 個字元是 2。

要知道第 266266 個字元落在正整數 125125 裡面，我們可以透過觀察分析：

  • 一位數有 11 到 99，共 99 個數字，佔去了前 99 個字元；
  • 二位數有 1010 到 9999，共 9090 個數字，佔去了接下來共 180180 個字元；
  • 三位數有 100100 到 999999，共 900900 個數字，又佔去了接下來共 27002700 個字元。

而 189<266≤2889189 < 266 \le 2889，表示第 266266 個字元超過了整個一位數與二位數的區域，落在某個三位數裡面。而又因為 25⋅3<266−189≤26⋅3,25 \cdot 3 < 266 - 189 \le 26 \cdot 3, 我們知道第 266266 個字元又恰好超過了 2525 個三位數，落在第 2626 個三位數裡，那就是在正整數 125125 裡面。更進一步因為 266−189−25⋅3=2,266 - 189 - 25 \cdot 3 = 2, 我們能知道它是正整數 125125 從高位開始算起的第 22 位數，也就是 2。

把這個流程一般化。我們可以發現 ℓ\ell 位數的正整數有 10ℓ−110^{\ell-1} 到 10ℓ−110^\ell - 1，共 9⋅10ℓ−19 \cdot 10^{\ell-1} 個數字。如果說第 kk 個字元落在某個 ℓ\ell 位數裡面，那 ℓ\ell 就滿足 (∑i=1ℓ−19i⋅10i−1)<k≤(∑i=1ℓ9i⋅10i−1)\Bigl(\displaystyle\sum_{i=1}^{\ell-1} 9i \cdot 10^{i-1}\Bigr) < k \le \Bigl(\sum_{i=1}^\ell 9i \cdot 10^{i-1}\Bigr) 接著找到 ss 使得 sℓ<k−(∑i=1ℓ−19i⋅10i−1)≤(s+1)ℓ, s\ell < k - \Bigl(\displaystyle\sum_{i=1}^{\ell-1} 9i \cdot 10^{i-1}\Bigr) \le (s+1)\ell, 就代表第 kk 個字元落在第 (s+1)(s+1) 個 ℓ\ell 位數裡面，也就是在正整數 n=10ℓ−1+sn = 10^{\ell-1} + s 裡面。更進一步它會是正整數 nn 從高位開始算起的第 k−(∑i=1ℓ−19i⋅10i−1)−sℓk - \Bigl(\displaystyle\sum_{i=1}^{\ell-1} 9i \cdot 10^{i-1}\Bigr) - s\ell 位數。

範例程式碼​

C++ 範例 
#include <iostream>
#define int long long
using namespace std;

signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int q, k;
    cin >> q;
    while (q--) {
        cin >> k;
        int lv = 1, ten = 1;
        while (k >= lv * 9 * ten) {
            k -= lv * 9 * ten;
            lv++;
            ten *= 10;
        }
        int s = (k-1) / lv;
        int n = ten + s;
        for (int i = lv; i > k - s*lv; i--) {
            n /= 10;
        }
        cout << n % 10 << '\n';
    }
}